|
In mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove Szemerédi's theorem, and in he proved the full lemma. Extensions of the regularity method to hypergraphs were obtained by Rödl and his collaborators〔.〕〔.〕〔.〕 and Gowers.〔.〕〔.〕 ==Formal statement of the regularity lemma== The formal statement of Szemerédi's regularity lemma requires some definitions. In what follows is a graph with vertex set . Definition 1. Let be disjoint subsets of . The density of the pair is defined as: Definition 2. For , a pair of vertex sets and is called -pseudo-random, if for all subsets , satisfying , , we have Definition 3. A partition of into sets: , is called an -regular partition, if: Now we can state the lemma: Regularity Lemma. For every and positive integer there exists an integer such that if is a graph with at least vertices, there exists an integer in the range and an -regular partition of the vertex set of into sets. It is a common variant in the definition of an -regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set whose size is at most an -fraction of the size of the vertex set of . The bound for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a -level iterated exponential of . At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However found examples of graphs for which does indeed grow very fast and is at least as large as a -level iterated exponential of . In particular the best bound has level exactly 4 in the Grzegorczyk hierarchy, and so is not an elementary recursive function. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Szemerédi regularity lemma」の詳細全文を読む スポンサード リンク
|